#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 13
const int INF = 1<<30;

int n,m;
int g[maxn][maxn];
int f[1<<maxn];
int dis[maxn];
int ans=INF;

void dfs(int state){
	for(int i=1;i<=n;i++){
		if((1<<(i-1))&state){
			for(int j=1;j<=n;j++){
				if(((1<<(j-1))&state)==0 && g[i][j]<INF){
					if(f[state|(1<<(j-1))] > f[state]+g[i][j]*dis[i]){
						f[state|(1<<(j-1))] = f[state]+g[i][j]*dis[i];
						int temp = dis[j];
						dis[j] = dis[i]+1;
						dfs(state|(1<<(j-1)));
						dis[j]=temp;
					}
				}
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=INF;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=min(g[u][v],w);
		g[v][u]=min(g[v][u],w);
	}
	for(int start=1;start<=n;start++){
		for(int j=0;j<=1<<n;j++) f[j]=INF;
		for(int j=0;j<=n;j++) dis[j]=INF;
		dis[start]=1;
		f[1<<(start-1)]=0;
		dfs(1<<(start-1));
		ans=min(ans,f[(1<<n)-1]);
	}
	cout<<ans<<endl;
	return 0;
}
